#include <iostream>
#include <queue>
#include <cstring>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INF 1<<20
#define NIL -1
using namespace std;
//图类,使用邻接矩阵实现，这里只考虑了简单无向加权图
class Graph
{
    private:
        int V;//图包含点数
        int *color; //颜色
	    int ** matrix;
        int *pai;//保存前驱
        int *disc;//保存开始处理点的时间
        int *finish;//保存结束处理点的时间
        int time;//保存DFS处理时的时间
        int *topo;  //保存拓扑排序中的节点
        int topoIndex;//拓扑排序数组中当前的位置
        //递归调用的内部DFS方法
        void DFS_VISIT(int u,bool second=false);
	public:

        //根据点数构造图
		Graph(int V);

        //析构函数
        ~Graph();
        //根据起点和终点构造一条边
        void addEdge(int start,int end,int weight=1);

        //判断两点之间是否有边
        bool adjecent(int a,int b);

        //打印图信息
        void printMap();

        //外部调用的DFS接口
        void DFS(bool second=false);

        //打印DFS结果
        void printDFS();
        
        //打印拓扑排序结果
        void printTopo();
        
        //转置图
        void transpos();
};
